1. Field of the Invention
The present invention relates to a technology for digital signature authentication.
2. Description of the Related Art
It has become a common practice to install a security camera in shops, downtown areas, and apartments, or to install a drive recorder in commercial vehicles. Accordingly, moving images are increasingly used as an evidential matter. Moreover, it has also become common to keep a record of conversation between a customer and an operator to deal with troubles in telephone transactions or in a customer support operation.
Currently, when a moving image or audio data is used as an evident, a video tape, an image, or an audio file is provided as it is. However, if stored images and audio data are digitized, it becomes easy to tamper or edit such data. Therefore, third-party authentication such as a signature and a timestamp becomes necessary. A service and a product to record sound of a telephone operator are actually provided, and needs for such a technology are expected to increase.
On the other hand, protection of privacy is another problem for increasing security cameras in using a shot image, and is discussed. In addition, since Private Information Protection Law is enforced, use of private information of an individual has been strictly limited and disclosure or partial deletion of information is required if the individual requests.
To protect privacy while maintaining adequacy as an evidential matter, a signature technology is studied in which partial guaranteeing of an original content is enabled that guarantees a part of an electronic document to maintain its original content, and in which concealment of a part of the electronic document is enabled. A signature technique in which addition, alteration, concealment (sanitization), and deletion are enabled on a part of a document to which a digital signature is applied while guaranteeing that the document maintains its original content is disclosed in the third Forum of Information Technology FIT 2004, M-066, 2004, “Proposal of a Partial Integrity Assurance Technology Considering Correction and Circulation of Electronic Documents” by Takashi Yoshioka and Masahiko Takenaka, and in Japanese Patent Laid-Open Publication No. 2006-60722.
By using such a technique, signature verification of a digital-signed electronic document becomes possible even in a state where a part of the document is concealed. Furthermore, it is possible to verify that no change has been made in the document except a concealed part (also “altered part” or “added part” in the technique disclosed in “Proposal of a Partial Integrity Assurance Technology Considering Correction and Circulation of Electronic Documents”) by a third party.
The signature technique disclosed in “Proposal of a Partial Integrity Assurance Technology Considering Correction and Circulation of Electronic Documents” is explained. This signature technique is a partial integrity assurance technology called PIAT, and partial integrity assurance of electronic data being a subject of signature is performed in a trilateral model of a signer, an extractor, and a verifier.
The signer is a person that digitally signs electronic data being a subject of signature, or a computer that is operated by the person. The signer guarantees a content of the electronic data by signing the data. It is necessary to sign the data under such a condition that which part is to be extracted from the subject of signature is unpredictable.
The extractor is a person that extracts (conceals or alters) a part from the electronic data being a subject of signature, or a computer that is operated by the person. The extractor extracts a part of the electronic data digitally signed by the signer and discloses the extracted part to the verifier. The extracted electronic data is referred to as extraction data. There are two kinds of extracting methods, onymous extraction and anonymous extraction. In the anonymous extraction, the extractor performs an extracting process under anonymity. In the onymous extraction, the extractor discloses information on the extractor so that who has performed the extracting process is specified.
The verifier is a person that verifies whether the extraction data is guaranteed by the signer, or a computer that is operated by the person. In the case of the anonymous extraction, it is verified whether the extraction data is a part of the electronic data signed by the signer. In the case of the onymous extraction, it is verified whether the extracting process is performed by the extractor as well as whether the extraction data is a part of the electronic data signed by the signer.
FIG. 22 is a schematic diagram showing an outline of algorism for a signer in PIAT. The signer divides an electronic document (entire character string) 2200 into partial data (character strings of respective lines), and calculates a hash value of each partial data to create a hash value set 2201. The digital signature of the signer is given to the hash value set 2201. A combination of the hash value set 2201 and a digital signature 2202 of the signer is a PIAT signature 2203 of the signer.
FIG. 23 is a schematic diagram showing an outline of algorism for an extractor in PIAT. The extractor extracts partial data (extraction data 2300) from the data to which the PIAT signature is given by the signer. Thereafter, the extractor performs the same operation as that performed by the signer. A combination of a hash value set 2301 thus obtained and a digital signature 2302 of the extractor is a PIAT signature 2303 of the extractor. When a deleted part is wished to be specified, a concealing process is performed, and partial data after deletion is modified to partial data, such as “XXXXXXX”, that can be identified as concealment.
FIG. 24 is a schematic diagram showing an outline of algorism for a verifier in PIAT. The verifier first verifies integrity of the hash value sets 2201 and 2301 from the PIAT signatures of the signer and the extractor. The verifier then creates a hash value set 2301 from the disclosed extraction data 2300, and verifies whether the hash value set 2301 thus created and the hash value set 2301 included in the PIAT signature 2303 of the extractor coincide with each other.
Finally, the verifier compares the hash value set 2201 of the signer and the hash value set 2301 of the extractor. It is found that a position of data at which the hash value is identical in both of the hash value sets 2201 and 2301 is a position of data extracted from the electronic document. If the hash value set 2301 of the extraction data 2300 is not included in the hash value set 2201 of the PIAT signature 2203 of the signer, it is determined that the extraction data 2300 is tampered.
In PIAT, extraction is performed basically by the onymous extraction, and therefore, it is possible to verify who has extracted which part. However, in the case of the anonymous extraction, the PIAT signature process performed by the extractor can be omitted. In this case, the verifier performs verification of the hash value set in the PIAT signature of the signer and the digital signature thereof, creation of a hash value set from the disclosed extraction data, and comparison with the hash value set in the PIAT signature of the signer.
This signature technique (PIAT) can be applied also to streaming data including a moving image file such as moving picture experts group phase 1 (MPEG-1) and an audio file.
In this case, streaming data being a subject of signature is divided into partial data. When streaming data of MPEG-1 is divided into partial data so as to be extractable, the data can be divided in an image unit or in a group of picture (GOP) unit.
However, in MPEG-1, since an interframe prediction technology is applied, P-frame and B-frame lack independency in an image unit. Therefore, extraction is considered to be limited. On the other hand, GOP is a smallest unit of a moving image in which several images are combined, and independent reproduction in this unit is possible. GOP is a structure for reproducing or editing a moving image from a middle of data. For simplicity, it is assumed that division into partial data is performed in the GOP unit.
The signer divides a moving image (for example, an MPEG-1 file) being a subject of signature in GOP units, and calculates a hash value of each GOP to create a hash value set. The signer then gives a digital signature of the signer to the created hash value set, to create a PIAT signature by combining the hash value set and the digital signature.
The extractor extracts a required partial moving image from the moving image to which the PIAT signature is given by the signer. In the case of the anonymous extraction, the extractor discloses the extracted moving image and the PIAT signature of the signer. In the case of the onymous extraction, the extractor performs the same operation as that performed by the signer, to create a PIAT signature of the extractor, and discloses the extracted moving image, the PIAT signature of the signer, and the PIAT signature of the extractor.
In the case of the onymous extraction, the verifier first verifies integrity of the hash value set from the PIAT signature of the signer and the PIAT signature of the extractor. The verifier then creates a hash value set from the disclosed extracted moving image, and verifies that the hash value set thus created coincides with the hash value set included in the PIAT signature of the extractor.
Finally, the verifier compares the hash value set of the signer and the hash value set of the extractor. It is found that a position of data at which the hash value is identical in both of the hash value sets is a position of data extracted from the moving image being the subject of signature. In the case of the anonymous extraction, the verifier performs verification of the hash value set in the PIAT signature of the signer and the digital signature thereof, creation of a hash value set from the disclosed extracted moving image, and comparison with the hash value set in the PIAT signature of the signer, to check whether it is partial information.
Next, the signature technique disclosed in Japanese Patent Laid-Open Publication No. 2006-60722 is explained. In this signature technique, an amount of data related to signature can be reduced by managing hash values, which are a part of the data related to signature, in a binary tree, and data to be a subject of signature includes not only electronic documents but also streaming data such as a moving image and audio data, similarly to PIAT described above. Herein, an example in which the subject of signature is streaming data of a moving image is explained.
FIG. 25 is a schematic diagram for explaining a signing process performed by a signer in the signature technique disclosed in Japanese Patent Laid-Open Publication No. 2006-60722 in which streaming data of a moving image is the subject of signature. In this technique, hash values h1 to h5 of partial moving images f1 to f5 obtained by dividing a moving image file F being a subject of the signature by GOP units are managed in a complete binary tree. This requires addition of dummy data D.
The signer first adds the dummy data D at the end of the moving image file F, and calculates hash values h1 to h8 for each GOP as a process of the first level. As a process of the second level, the signer then connects the end of a hash value hx and the head of hy to calculate a new hash value hx,y. The hash value hx and the hash value hy are adjacent values.
The same process is repeated in the third level and later until a single hash value is obtained. Thus, a hash-value binary tree T is created. The single hash value is referred to as root Ra. In the example shown in FIG. 25, the root Ra is obtained in the fourth level. The signer gives a digital signature Sa of the signer to the root Ra.
Disclosure information A that is stored at this time includes the original moving image file F, the dummy data D (or a root hash value string {h6, h7,8} having hash values of the partial moving images f6 to f8 of the dummy data D as leaves), and the root Ra to which the digital signature Sa is given.
FIG. 26 is a schematic diagram for explaining an extracting process performed by an extractor in the signature technique disclosed in Japanese Patent Laid-Open Publication No. 2006-60722 in which streaming data of a moving image is the subject of signature. The extractor extracts the partial moving images f3 and f4 from the moving image file F being a subject of signature, and calculates the hash values h1 to h8 of the partial moving images f1 to f8 of the moving image file F and the dummy data D as a process of the first level. The extractor then deletes all partial moving images f1, f2, and f5 to f8 except the extracted partial moving images f3 and f4.
Thereafter, the extractor connects the end of the hash value hx and the head of the hash value hy to create a new hash value hx,y, and repeats the same process in the second level and later until a single hash value is obtained. Thus, the hash-value binary tree T is created. In the example shown in FIG. 26, a root Rb is created with the hash value obtained in the fourth level. The extractor gives a digital signature Sb of the extractor to the root Rb.
Signature related data B disclosed at this time includes the extracted moving images f3 and f4, root hash values h1,2 and h5,8 that are obtained from the hash values of the deleted partial moving images f1, f2, and f5 to f8, and the root Rb to which the digital signature Sb is given.
However, in the signature technique described above, when a part of large streaming data such as a moving image file and an audio file is extracted, it is necessary to store all of hash values of moving images other than the extracted moving image. Therefore, an amount of data related to signature is enormous.
Moreover, in the signature technique disclosed in Japanese Patent Laid-Open Publication No. 2006-60722, although it is possible to reduce an amount of data related to signature by managing hash values, which are a part of the data related to signature, in a binary tree, addition of dummy data is required to manage the hash values in a complete binary tree.
Accordingly, an amount of data to be stored increases due to added dummy data D (the dummy data D or a hash value group of a hash tree T constituted only of the dummy data D).
Furthermore, since the dummy data D is added, calculation of hash values therefor is required, and as a result, a processing time also increases. In addition, falsification (curtailment) of the moving image file being the subject of signature is possible by replacing data at the end of the moving image file with the dummy data.
Moreover, random numbers that are included in the signature related data required to guarantee uniqueness of the extracted partial moving images f3 and f4 are also required to be stored as they are. FIG. 27 is a schematic diagram for showing random numbers that are added to the partial moving images f1 to f5. As shown in FIG. 27, although it is possible to unify the hash values h1 to h5 of the respective partial moving images f1 to f5 in units of GOP into a single hash value h, the same number of random numbers r1 to r5 as the number of the partial moving images f1 to f5 are required. As a result, an amount of the signature related data becomes enormous.
As described above, if PIAT is simply applied to streaming data such as a moving image file, even if a part of the data is extracted, the data can be guaranteed as a part of the moving image file being the subject of signature.
However, as described above, when the moving image file being the subject of signature is a moving image file with a long recording time or a moving image file having a high frame rate, the number of frames or GOP becomes large. As a result, an amount of data of a hash value set included in the PIAT signature increases.
Furthermore, when a content of the moving image file being the subject of signature is an animation, the same frame or GOP appears repeatedly. In PIAT, if the same image appears in partial data, a moving image corresponding to the deleted part can be restored based on a hash value set. To guarantee uniqueness of the partial data, if the same image appears in the partial data, a random number is required to be added for each of original partial data.
FIG. 28 is a schematic diagram showing a moving image file of an animation. As shown in FIG. 28, even if images E1 and E2 are deleted, when the hash values h1 to h3 of images E1 to E3 are the same, the deleted image E1 and E2 can be restored based on the hash value of the image E3 since the deleted images E1 and E2 are identical to the image E3. To prevent such restoration, it is necessary to add a random number to each of the images E1 and E4.
However, when random numbers are added, data of the number of GOP×random number length are further required to be stored. Therefore, data other than the moving images to be stored further increases. For example, when a PIAT signature is given to a moving image of one hour long having a frame rate equivalent to that of television, the signature data requires several hundred kilobytes to several megabytes. The amount of data is small compared to that of the image data, however, the amount of signature related data increases.